package com.hqq.exercise.tree;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Stack;

/**
 * FindTreePath 二叉树中和为某一值的路径
 * 题目描述:
 * 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径
 * 从树的根节点开始往下一直到叶结点所经过的结点形成一条路径
 * 样例输入
 * -------10
 * -----5    12
 * ---4  7
 * <p>
 * num:22
 * 样例输出:
 * 10 12
 * 10 5 7
 * Created by heqianqian on 2017/8/14.
 */
public class FindTreePath {

    private static final Logger LOGGER = LoggerFactory.getLogger(FindTreePath.class);

    public static void findPath(TreeNode root, int num) {
        if (root == null) {
            LOGGER.info("树为空!");
            return;
        }
        Stack<Integer> stack = new Stack<>();
        int countSum = 0;

        findPath(root, num, stack, countSum);
    }

    private static void findPath(TreeNode root, int num, Stack<Integer> stack, int countSum) {
        countSum += root.val;
        stack.push(root.val);

        if (root.left == null && root.right == null) {
            //如果当前节点是叶子节点 则判断是否满足要求
            if (num == countSum) {
                LOGGER.info("找到一条路径: ");
                for (int i = 0; i < stack.size(); i++) {
                    LOGGER.info("{} ",stack.get(i));
                }
                System.out.println();
            }
        }

        //不是叶子节点就继续遍历
        if (root.left != null) {
            findPath(root.left, num, stack, countSum);
        }
        if (root.right != null) {
            findPath(root.right, num, stack, countSum);
        }
        stack.pop();
    }
}
